Usenet 1993 July

home *** CD-ROM | disk | FTP | other *** search

/ Usenet 1993 July / InfoMagic USENET CD-ROM July 1993.ISO / sources / misc / volume10 / b+tree_mjr / part02 < prev next >

Wrap

Text File | 1990-01-19 | 59.0 KB | 2,186 lines

Newsgroups: comp.sources.misc subject: v10i028: B+tree library, part02 of 5 from: mjr@umiacs.UMD.EDU (Marcus J. Ranum) Sender: allbery@uunet.UU.NET (Brandon S. Allbery - comp.sources.misc) Posting-number: Volume 10, Issue 28 Submitted-by: mjr@umiacs.UMD.EDU (Marcus J. Ranum) Archive-name: b+tree_mjr/part02 #! /bin/sh # This is a shell archive. Remove anything before this line, then unpack # it by saving it into a file and typing "sh file". To overwrite existing # files, type "sh file -c". You can also feed this as standard input via # unshar, or by typing "sh <file", e.g.. If this archive is complete, you # will see the following message at the end: # "End of archive 2 (of 5)." # Contents: b+tree/COPYRIGHT b+tree/btdbmlib/Makefile # b+tree/btdbmlib/README b+tree/btdbmlib/stalloc.c # b+tree/btdbmlib/stlinkb.c b+tree/btdbmlib/store.h # b+tree/btdbmlib/strealloc.c b+tree/btlib/README # b+tree/btlib/btconf.h b+tree/btlib/btdebug.c # b+tree/btlib/btdelete.c b+tree/btlib/btload.c # b+tree/btlib/btopen.c b+tree/btlib/btravrs.c b+tree/btlib/btree.h # b+tree/utils/Makefile b+tree/utils/README b+tree/utils/btoptim.c # Wrapped by mjr@atreus on Fri Jan 19 10:34:58 1990 PATH=/bin:/usr/bin:/usr/ucb ; export PATH if test -f 'b+tree/COPYRIGHT' -a "${1}" != "-c" ; then echo shar: Will not clobber existing file \"'b+tree/COPYRIGHT'\" else echo shar: Extracting \"'b+tree/COPYRIGHT'\" $1688 characters$ sed "s/^X//" >'b+tree/COPYRIGHT' <<'END_OF_FILE' X X X (C) Copyright, 1988, 1989 Marcus J. Ranum X All rights reserved X X XThis software, its documentation, and supporting files may Xbe distributed and modified freely subject to the following Xconditions: X X1) None of the copyright headers in any of the files may be Xaltered in any way. X X2) This software is not to be incorporated into another Xsoftware package or operating system that is sold for a fee, Xor is "shareware", without the author's written consent, Xunless the source code to this software is included with Xthat package, or a notice is included stating that this Xsoftware is available without a fee, who wrote it, and where Xto look for it. X X3) This software may not be distributed in binary-only Xformat, unless a notice is included stating that this Xsoftware is available without a fee, and where to look for Xit. X X4) This software may not be redistributed in any manner that Xincludes a handling charge, without the author's written Xconsent. X X5) This software may not be redistributed without its Xdocumentation and supporting files. X X XUsers are encouraged to modify this software and improve it, Xand to share those improvements with others. If you feel you Xhave improved it, please contact the author, if you want to Xshare your improvements. Please inform the author of bugs or Xbug fixes. X X XThe author assumes no liability for the use or misuse of Xthis software, and makes no claims as to its suitability for Xany purpose. Do not take internally. See a physician Ximmediately if accidentally ingested. X X XMarcus J. Ranum X3018 Guilford Ave XBaltimore, Md 21218 X X X Dec 19, 1989 END_OF_FILE if test 1688 -ne `wc -c <'b+tree/COPYRIGHT'`; then echo shar: \"'b+tree/COPYRIGHT'\" unpacked with wrong size! fi # end of 'b+tree/COPYRIGHT' fi if test -f 'b+tree/btdbmlib/Makefile' -a "${1}" != "-c" ; then echo shar: Will not clobber existing file \"'b+tree/btdbmlib/Makefile'\" else echo shar: Extracting \"'b+tree/btdbmlib/Makefile'\" $1863 characters$ sed "s/^X//" >'b+tree/btdbmlib/Makefile' <<'END_OF_FILE' X# X# X#/* X# (C) Copyright, 1988, 1989 Marcus J. Ranum X# All rights reserved X# X# X# This software, its documentation, and supporting X# files are copyrighted material and may only be X# distributed in accordance with the terms listed in X# the COPYRIGHT document. X#*/ X# X# $Header: /atreus/mjr/hacks/btree/btdbmlib/RCS/Makefile,v 1.1 89/10/24 10:09:23 mjr Rel $ X# X XBTHDRDIR=../btlib XDBHDRDIR=. X X# compiler to use XCC= cc X X#CFLAGS = -I$(BTHDRDIR) -I$(DBHDRDIR) -g X#CFLAGS = -I$(BTHDRDIR) -I$(DBHDRDIR) -p XCFLAGS = -I$(BTHDRDIR) -I$(DBHDRDIR) -O X XLDFLAGS= -g X X# where to build the library. must be set in testrack/Makefile X# if you change it from here. XLIBDIR=.. XLIB= $(LIBDIR)/libbtdbm.a X XCFILES= btdbmclose.c \ X btdbmdelete.c \ X btdbmfetch.c \ X btdbmfirstkey.c \ X btdbmnextkey.c \ X btdbmopen.c \ X btdbmstore.c \ X stalloc.c \ X stclose.c \ X stcopy.c \ X stdecref.c \ X sterrs.c \ X stfree.c \ X stgethed.c \ X stincref.c \ X stlinka.c \ X stlinkb.c \ X stopen.c \ X stputhed.c \ X stread.c \ X strealloc.c \ X streallocbuf.c \ X stunlink.c \ X stwrite.c \ X stwsuper.c X XHFILES= btdbm.h \ X stoconf.h \ X store.h \ X stointern.h X XOFILES= btdbmclose.o \ X btdbmdelete.o \ X btdbmfetch.o \ X btdbmfirstkey.o \ X btdbmnextkey.o \ X btdbmopen.o \ X btdbmstore.o \ X stalloc.o \ X stclose.o \ X stcopy.o \ X stdecref.o \ X sterrs.o \ X stfree.o \ X stgethed.o \ X stincref.o \ X stlinka.o \ X stlinkb.o \ X stopen.o \ X stputhed.o \ X stread.o \ X strealloc.o \ X streallocbuf.o \ X stunlink.o \ X stwrite.o \ X stwsuper.o X XFILES= $(CFILES) \ X $(HFILES) \ X README \ X Makefile X X$(LIB): $(OFILES) X ar crv $(LIB) $(OFILES) X ranlib $(LIB) X X$(OFILES): $(HFILES) X Xclean: X rm -f *.o $(LIB) core tags rectest X Xci: X ci -u $(FILES) < /dev/null X Xtags: X ctags $(CFILES) X Xlint: $(CFILES) X lint -I$(BTHDRDIR) -I$(DBHDRDIR) -u $(CFILES) | sed '/pointer alignment/d' X END_OF_FILE if test 1863 -ne `wc -c <'b+tree/btdbmlib/Makefile'`; then echo shar: \"'b+tree/btdbmlib/Makefile'\" unpacked with wrong size! fi # end of 'b+tree/btdbmlib/Makefile' fi if test -f 'b+tree/btdbmlib/README' -a "${1}" != "-c" ; then echo shar: Will not clobber existing file \"'b+tree/btdbmlib/README'\" else echo shar: Extracting \"'b+tree/btdbmlib/README'\" $2690 characters$ sed "s/^X//" >'b+tree/btdbmlib/README' <<'END_OF_FILE' X X X/* X (C) Copyright, 1988, 1989 Marcus J. Ranum X All rights reserved X X X This software, its documentation, and supporting X files are copyrighted material and may only be X distributed in accordance with the terms listed in X the COPYRIGHT document. X*/ X X X A few words about the arrangement of these modules:: X XContents:: XMakefile - obvious. XREADME - obvious. Xbtdbm.h - header for btree-based dbm clone. Xbtdbmclose.c - close function for btree-based dbm clone. Xbtdbmdelete.c - delete function. Xbtdbmfetch.c - fetch function. Xbtdbmfirstkey.c - first key function. Xbtdbmnextkey.c - key traversal function. Xbtdbmopen.c - open function. Xbtdbmstore.c - store function. Xstalloc.c - storage allocation function. Xstclose.c - storage file close function. Xstcopy.c - storage file record copy/duplication function. Xstdecref.c - storage file record reference count decrement fnction. Xsterrs.c - storage file error strings file, and perror functions. Xstfree.c - storage file free list manager. cryptic. Xstgethed.c - storage file record header reader. Xstincref.c - storage file record reference count increment fnction. Xstlinka.c - storage file linked-list management "link after" function. Xstlinkb.c - storage file linked-list management "link before" function. Xstoconf.h - configuration information for storage file library. Xstointern.h - internal macros for storage file library. not user level. Xstopen.c - storage file opening/initialization function. Xstore.h - main header for storage file library. Xstputhed.c - storage file record header updater. Xstread.c - storage file "read-like" function. Xstrealloc.c - storage file record reallocation/copy function. Xstunlink.c - storage file linked-list management unlink function. Xstwrite.c - storage file "write-like" function. Xstwsuper.c - storage file super-block updater function. X XNotes: X There is some sleazy semi-optimization in the write/read routines, Xsince the header is read before the read or write, we know we don't have to Xre-seek before we actually do the read. This saves us a seek, so we do it, Xthough if the layout of the record headers changes, things will get evil. X X For a detailed description of how the free list is managed, see Xstfree.c X X XTo Do: X1) Possibly add some form of record header caching. The current way makes Xtoo many system calls (about 4 per operation). X X2) Possibly add some form of file seek caching as well. Storing the location Xof the file pointer might save a few system calls. X X3) improve the btdbm library to use linked lists for multiple records with Xthe same key. X X4) improve the btdbm library to use more of the b+tree functionality. X X--mjr(); END_OF_FILE if test 2690 -ne `wc -c <'b+tree/btdbmlib/README'`; then echo shar: \"'b+tree/btdbmlib/README'\" unpacked with wrong size! fi # end of 'b+tree/btdbmlib/README' fi if test -f 'b+tree/btdbmlib/stalloc.c' -a "${1}" != "-c" ; then echo shar: Will not clobber existing file \"'b+tree/btdbmlib/stalloc.c'\" else echo shar: Extracting \"'b+tree/btdbmlib/stalloc.c'\" $3466 characters$ sed "s/^X//" >'b+tree/btdbmlib/stalloc.c' <<'END_OF_FILE' X#include <sys/types.h> X#include "stoconf.h" X#include "store.h" X#include "stointern.h" X X X/* X (C) Copyright, 1988, 1989 Marcus J. Ranum X All rights reserved X X X This software, its documentation, and supporting X files are copyrighted material and may only be X distributed in accordance with the terms listed in X the COPYRIGHT document. X*/ X X X#ifndef lint Xstatic char *rcsid = "$Header: /atreus/mjr/hacks/btree/btdbmlib/RCS/stalloc.c,v 1.1 89/10/24 10:09:12 mjr Rel $"; X#endif X X/* X storage allocation for the store library. allocation is performed X as follows: X 1) if there is a free header list, read it sequentially and take X the first fit. X a)if the first fitting record is bigger than some compiled-in X value, it is split into 2 subrecords, and the left-over X is placed back into the free list. X b)if the first fitting record is not large enough to split X without excessive fragmentation, return the whole thing X and assume the user will be happy. X 2) if there is no free header list, allocate a new record chunk X from the end-of-file and initialize it as empty. X X the free header list is stored as a record, and is accessed and X updated by library routines. it's somewhat self-referential, but X works nicely. the only disadvantage of this approach is that it X probably does more seeks than it should in an ideal world. X*/ X X Xsto_ptr Xstore_alloc(r,bytes) XSTORE *r; Xint bytes; X{ X sto_ptr ret = STO_NULL; X struct sto_hdr rbuf; X X if(bytes <= 0) X return(STO_NULL); X X if(r->sblk.free != STO_NULL) { X struct sto_freeent fry; X struct sto_freeent *freep; X int byt; X off_t currof; X int ismore; X int fcnt; X int junk; X X currof = (off_t)(2 * sizeof(long)); X X while(1) { X X ismore = store_read(r,r->sblk.free,currof,store_buffer(r),store_bufsiz(r),&byt); X if(ismore == STO_ERR) X return(STO_ERR); X X if(currof == 0L) { X freep = STO_FREEBUF(store_buffer(r)); X fcnt = ((byt - (2 * sizeof(off_t))) / STO_FSIZ); X } else { X freep = (struct sto_freeent *)store_buffer(r); X fcnt = byt / STO_FSIZ; X } X X currof += (off_t)byt; X X for(junk = 0; junk < fcnt; junk++) { X if(bytes <= freep->size) { X X /* allocate it */ X ret = freep->addr; X X /* if the block is big enough, split */ /* it into a record of the desired */ /* size and one consisting of the */ X /* left-overs. if the size of the */ X /* table scraps is small, just give */ X /* the customer a bit extra */ X if(freep->size - bytes >= STO_SPLITSIZ) { X fry.addr = freep->addr + STO_HSIZ + bytes; X X fry.size = freep->size - (2 * STO_HSIZ) - bytes; X rbuf.size = bytes; X } else { X fry.addr = STO_NULL; X fry.size = 0; X rbuf.size = freep->size; X } X X if(store_write(r,r->sblk.free,(off_t)(2 * sizeof(off_t) + (junk * STO_FSIZ)),(unsigned char *)&fry,STO_FSIZ) == STO_ERR) X return(STO_NULL); X X /* duh, break out of the loop */ X junk = fcnt + 1; X } X freep++; X } X if(ismore != STO_MORE) X break; X } X X } X X if(ret == STO_NULL) { X ret = r->sblk.high; X r->sblk.high += bytes + STO_HSIZ; X rbuf.size = bytes; X rbuf.used = 0; X rbuf.refs = 1; X rbuf.next = rbuf.prev = STO_NULL; X if(store_wsuper(r) != STO_OK) X return(STO_NULL); X } X X rbuf.magic = STO_DFLTMAGIC; X rbuf.used = 0; X rbuf.refs = 1; X rbuf.next = rbuf.prev = STO_NULL; X X if(store_puthdr(r,ret,&rbuf) == STO_ERR) X return(STO_NULL); X X return(ret); X} END_OF_FILE if test 3466 -ne `wc -c <'b+tree/btdbmlib/stalloc.c'`; then echo shar: \"'b+tree/btdbmlib/stalloc.c'\" unpacked with wrong size! fi # end of 'b+tree/btdbmlib/stalloc.c' fi if test -f 'b+tree/btdbmlib/stlinkb.c' -a "${1}" != "-c" ; then echo shar: Will not clobber existing file \"'b+tree/btdbmlib/stlinkb.c'\" else echo shar: Extracting \"'b+tree/btdbmlib/stlinkb.c'\" $1610 characters$ sed "s/^X//" >'b+tree/btdbmlib/stlinkb.c' <<'END_OF_FILE' X#include <sys/types.h> X#include "stoconf.h" X#include "store.h" X X X/* X (C) Copyright, 1988, 1989 Marcus J. Ranum X All rights reserved X X X This software, its documentation, and supporting X files are copyrighted material and may only be X distributed in accordance with the terms listed in X the COPYRIGHT document. X*/ X X X#ifndef lint Xstatic char *rcsid = "$Header: /atreus/mjr/hacks/btree/btdbmlib/RCS/stlinkb.c,v 1.1 89/10/24 10:09:16 mjr Rel $"; X#endif X X/* X manipulate the link pointers of a header to link the record numbered X 'pred' BEFORE the record numbered 'victim'. Note that no attempt is X made to UNLINK the victim if it is already linked into a list. X that must be controlled at a higher level, or we get into a kind X of recursive linking and unlinking loop and never return. X*/ X Xstore_linkbefore(r,victim,next) XSTORE *r; Xsto_ptr victim; Xsto_ptr next; X{ X struct sto_hdr nbuf; X struct sto_hdr pbuf; X struct sto_hdr vbuf; X char pnul = 0; X X if(next == STO_NULL) { X store_errno(r) = STO_NOREC; X return(STO_ERR); X } X X if(store_gethdr(r,victim,&vbuf) == STO_ERR || store_gethdr(r,next,&nbuf) == STO_ERR) X return(STO_ERR); X X if(nbuf.prev != STO_NULL) X pnul++; X X if(pnul && store_gethdr(r,nbuf.prev,&pbuf) == STO_ERR) X return(STO_ERR); X X if(pnul) X pbuf.next = victim; X vbuf.next = next; X vbuf.prev = nbuf.prev; X nbuf.prev = victim; X X if(store_puthdr(r,victim,&vbuf) == STO_ERR || store_puthdr(r,next,&nbuf) == STO_ERR) X return(STO_ERR); X X if(pnul && store_puthdr(r,vbuf.prev,&pbuf) == STO_ERR) X return(STO_ERR); X X return(STO_OK); X} END_OF_FILE if test 1610 -ne `wc -c <'b+tree/btdbmlib/stlinkb.c'`; then echo shar: \"'b+tree/btdbmlib/stlinkb.c'\" unpacked with wrong size! fi # end of 'b+tree/btdbmlib/stlinkb.c' fi if test -f 'b+tree/btdbmlib/store.h' -a "${1}" != "-c" ; then echo shar: Will not clobber existing file \"'b+tree/btdbmlib/store.h'\" else echo shar: Extracting \"'b+tree/btdbmlib/store.h'\" $1913 characters$ sed "s/^X//" >'b+tree/btdbmlib/store.h' <<'END_OF_FILE' X#ifndef _DEF_STO_H X X/* X (C) Copyright, 1988, 1989 Marcus J. Ranum X All rights reserved X X X This software, its documentation, and supporting X files are copyrighted material and may only be X distributed in accordance with the terms listed in X the COPYRIGHT document. X*/ X X X/* X $Header: /atreus/mjr/hacks/btree/btdbmlib/RCS/store.h,v 1.1 89/10/24 10:09:20 mjr Rel $ X*/ X X#define STO_NULL -1L X X#define STO_OK 0 X#define STO_ERR 1 X#define STO_MORE 2 X X/* STARTING size of the store file internal buffer */ X/* this is also the size of the initial free list block */ X#define STO_BUFSIZ 1024 X Xtypedef off_t sto_ptr; X X/* a record header. one before each record in the file */ Xstruct sto_hdr { X off_t magic; X int size; X int used; X int refs; X sto_ptr next; X sto_ptr prev; X}; X X/* store file super block */ Xstruct sto_sb { X off_t magic; X off_t high; X sto_ptr free; X sto_ptr label; X}; X Xstruct store_hand { X int fd; X int errno; X sto_ptr currec; /* current record */ X sto_ptr curlst; /* current list head */ X struct sto_sb sblk; X int bufsiz; /* buffer size */ X unsigned char *buf; /* general porpoise buffer */ X /* this buffer may "stretch" to */ X /* accomodate data */ X}; X#define STORE struct store_hand X X/* pseudo-functions */ X#define store_errno(r) (r->errno) X#define store_clearerr(r) (r->errno = STO_NOERROR) X#define store_fileno(r) (r->fd) X#define store_buffer(r) (r->buf) X#define store_bufsiz(r) (r->bufsiz) X#define store_currec(r) (r->currec) X#define store_label(r) (r->sblk.label) X X/* forward decls */ Xextern STORE *store_open(); Xextern sto_ptr store_alloc(); Xextern sto_ptr store_realloc(); Xextern void store_perror(); X X/* error codes and messages */ Xextern char *sto_errs[]; X X/* error constants */ X#define STO_NOERROR 0 X#define STO_BADHDR 1 X#define STO_IOERR 2 X#define STO_NOREC 3 X#define STO_TOOSMALL 4 X X#define _DEF_STO_H X#endif END_OF_FILE if test 1913 -ne `wc -c <'b+tree/btdbmlib/store.h'`; then echo shar: \"'b+tree/btdbmlib/store.h'\" unpacked with wrong size! fi # end of 'b+tree/btdbmlib/store.h' fi if test -f 'b+tree/btdbmlib/strealloc.c' -a "${1}" != "-c" ; then echo shar: Will not clobber existing file \"'b+tree/btdbmlib/strealloc.c'\" else echo shar: Extracting \"'b+tree/btdbmlib/strealloc.c'\" $1870 characters$ sed "s/^X//" >'b+tree/btdbmlib/strealloc.c' <<'END_OF_FILE' X#include <sys/types.h> X#include "stoconf.h" X#include "store.h" X X X/* X (C) Copyright, 1988, 1989 Marcus J. Ranum X All rights reserved X X X This software, its documentation, and supporting X files are copyrighted material and may only be X distributed in accordance with the terms listed in X the COPYRIGHT document. X*/ X X X#ifndef lint Xstatic char *rcsid = "$Header: /atreus/mjr/hacks/btree/btdbmlib/RCS/strealloc.c,v 1.1 89/10/24 10:09:17 mjr Rel $"; X#endif X X/* X record reallocator. this has to do a lot of ugly stuff because of X the linked-list management. first it remembers the sibs of a record, X allocates a new one, copies the old one into it, frees the old one, X patches links and references and returns. X*/ X Xsto_ptr Xstore_realloc(r,rec,bytes) XSTORE *r; Xsto_ptr rec; Xint bytes; X{ X sto_ptr ret; X struct sto_hdr rbuf; X struct sto_hdr nbuf; X X /* remember this so we can patch any links that existed */ X if(store_gethdr(r,rec,&rbuf) == STO_ERR) X return(STO_ERR); X X ret = store_alloc(r,bytes); X if(ret == STO_NULL) X return(STO_NULL); X X if(store_copy(r,rec,ret) == STO_ERR) X return(STO_NULL); X X if(store_free(r,rec) == STO_ERR) X return(STO_NULL); X X /* re-establish next links */ X if(rbuf.next != STO_NULL) { X if(store_gethdr(r,rbuf.next,&nbuf) == STO_ERR) X return(STO_ERR); X nbuf.prev = ret; X if(store_puthdr(r,rbuf.next,&nbuf) == STO_ERR) X return(STO_ERR); X } X X /* re-establish prev links */ X if(rbuf.prev != STO_NULL) { X if(store_gethdr(r,rbuf.prev,&nbuf) == STO_ERR) X return(STO_ERR); X nbuf.next = ret; X if(store_puthdr(r,rbuf.prev,&nbuf) == STO_ERR) X return(STO_ERR); X } X X if(store_gethdr(r,ret,&nbuf) == STO_ERR) X return(STO_ERR); X X nbuf.refs = rbuf.refs; X nbuf.next = rbuf.next; X nbuf.prev = rbuf.prev; X X if(store_puthdr(r,ret,&nbuf) == STO_ERR) X return(STO_ERR); X return(ret); X} END_OF_FILE if test 1870 -ne `wc -c <'b+tree/btdbmlib/strealloc.c'`; then echo shar: \"'b+tree/btdbmlib/strealloc.c'\" unpacked with wrong size! fi # end of 'b+tree/btdbmlib/strealloc.c' fi if test -f 'b+tree/btlib/README' -a "${1}" != "-c" ; then echo shar: Will not clobber existing file \"'b+tree/btlib/README'\" else echo shar: Extracting \"'b+tree/btlib/README'\" $3983 characters$ sed "s/^X//" >'b+tree/btlib/README' <<'END_OF_FILE' X X X/* X (C) Copyright, 1988, 1989 Marcus J. Ranum X All rights reserved X X X This software, its documentation, and supporting X files are copyrighted material and may only be X distributed in accordance with the terms listed in X the COPYRIGHT document. X*/ X XTO COMPILE:: X edit btconf.h as necessary to reflect your system/preferences. X edit Makefile to fix any necessary flags. X XTO INSTALL:: X only btree.h and the library need to be placed in user-accessible X locations. X XTO TEST:: X build the library and check out the testing functions in ../utils. X if there is a catastrophic failure, you're on your own. X XContents:: Xbtree.h - needed by anything using the btree code. defines various X constants and macros, as well as forward declarations. Xbtconf.h - put system specific configuration stuff here. this file X contains compile-time options settings and system macros. Xbtintern.h - NEVER include this in user level code unless you know X bloody well what you're about. this file contains the X internal page structures and mystical secret stuff that X should never need to be edited. Xbtclose.c - function to close a btree. Xbtdelete.c - function to delete a key from a btree. Xbterrors.c - error strings and bt_perror(). Xbtfind.c - function to locate a key in a btree. Xbtgoto.c - function to go to first/last key of btree. Xbtinsert.c - insert function. Xbtio.c - cache manipulation routines, also functions for syncing X buffers, writing superblocks, and allocating and freeing X new pages. Xbtlabel.c - functions for manipulating a label hidden in free space X between first page and the end of the superblock. Xbtload.c - function for optimal load of reverse sorted keys. Xbtopen.c - simple btree opening function that doesn't provide much X in the way of options. Xbtoopen.c - btree opening function that provides access to every X option supported by the library. uses varargs and will X not compile on machines without varargs. Xbtpage1.c - first half of the internal page manipulation routines. X contains page search functions, page insert, and page X split. Xbtpage2.c - second half of the internal page manipulation routines. X contains page delete function, and a function to grab a X specific key/ptr pair out of a page. Xbtravrs.c - function to scan forward/backwards in btree. Xbtseek.c - internal function that navigates to leaf level. called X in bt_insert(), bt_delete(), bt_find(), etc. Xbtzap.c - function that resets an index. X XNotes: X1) stdio.h is not included in every module, and should not be. Unfortunately XI had to include it for NULL and BUFSIZ in a couple of places, but I hate Xhaving it wasting space when I compile stuff. X X2) btpage1.c and btpage2.c are separate because of the hairy use of macros Xand symbols that makes it hard to fit in the memory of a small compiler. Xplease keep them separate. X X3) static functions: I normally would make 99% of these functions static Xso they would not clutter up the name space, BUT, because of compiler Xspace constraints on my Amiga, and the fact that I want to be able to Xuse the page handling code in record management, I need access to them Xexternally. please do not change this. (though I may make a version of Xthis library that IS all staticed out, and all the code is in one BIG Xmodule. ick, poo.) X X4) library size: all these modules are carefully arranged so that no Xextraneous functions will get linked in (if your linker is not totally Xdead-brained). Please do not destroy that, since, IMHO, libraries should Xnever give you more than you need. X XTo Do: X1) make (if possible) the page insertion and manipulation routines Xmore portable. I simply don't know how to do this myself, so anyone Xwho knows how is invited to tell me! X X2) It would be nice if there was an EFFICIENT way to tell the tree to Xstore records off the leaves. This could be really bad, if it was not Ximplemented properly, though. If someone does this, or wants to, let Xme know. X X--mjr(); END_OF_FILE if test 3983 -ne `wc -c <'b+tree/btlib/README'`; then echo shar: \"'b+tree/btlib/README'\" unpacked with wrong size! fi # end of 'b+tree/btlib/README' fi if test -f 'b+tree/btlib/btconf.h' -a "${1}" != "-c" ; then echo shar: Will not clobber existing file \"'b+tree/btlib/btconf.h'\" else echo shar: Extracting \"'b+tree/btlib/btconf.h'\" $4357 characters$ sed "s/^X//" >'b+tree/btlib/btconf.h' <<'END_OF_FILE' X#ifndef _DEF_BT_CONFIG_H X X/* X (C) Copyright, 1988, 1989 Marcus J. Ranum X All rights reserved X X X This software, its documentation, and supporting X files are copyrighted material and may only be X distributed in accordance with the terms listed in X the COPYRIGHT document. X*/ X X X/* X $Header: /atreus/mjr/hacks/btree/btlib/RCS/btconf.h,v 1.1 89/10/24 10:09:07 mjr Rel $ X X THIS SHOULD NOT BE INCLUDED BY USER-LEVEL PROGRAMS X X All reasonably user-configurable options are in this file. X X If there is something that needs to be special-cased for X a system, put it here, PLEASE! X*/ X X X/* XWARNING - there is one option that *should* be there but is in Xbtree.h because it needs to be seen by user-level programs. XThat is the definition on bt_chrp, which is at the top of the Xfile. If you have a weird architecture, you may want to look Xat that value. X*/ X X X/* XSEEK_SET should be whatever your systems version of lseek() takes Xto tell it to go to an exact offset. zero is pretty standard. X*/ X#ifndef SEEK_SET X#define SEEK_SET 0 X#endif X X/* Xif this option is turned on the bt_dump() page dump function will Xbe generated. it probably should be left out of public libraries Xbut is really handy, and it would be stupid to have to rewrite it. X X#undef YES_BT_DEBUG X*/ X#define YES_BT_DEBUG 1 X X X/* Xapparently not all compilers handle register declarations intelligently. Xthe functions in btpage1.c and btpage2.c have register declarations, Xsometimes as many as six. if your compiler cannot handle them, just Xredefine REGISTER to be nothing. X X#define REGISTER X*/ X#define REGISTER register X X X/* Xchoose one of these as your favorite memory copying function Xcan you believe 3 functions, 3 names, all do the same thing ? X X#define USE_MEMCPY 1 X#define USE_MOVEMEM 1 X*/ X#define USE_BCOPY 1 X X/* Xif the operating system the software will be running under supports Xthe ftruncate(2) system call to free a file's allocated space after Xa certain length, turn this option on, and bt_zap() will free extra Xspace when called. X#define USE_FTRUNCATE 0 X*/ X#define USE_FTRUNCATE 1 X X/* Xthe default page size. usually use BUFSIZ or maybe (BUFSIZ * 2) Xconsiderations are:: as buffer size increases, memory use for Xcache buffers increases. on the other hand, speed increases, Xdepending on the size of the tree/keys/data type. disk wastage Xalso increases, since it is possible there may be partial pages Xtaking up more space than would be taken up with smaller pages. Xsmaller pages are a win if speed is less important than disk Xwastage, though decreasing page size and boosting cache may Xoffset speed losses. this is not something that can be guessed Xat, so use BUFSIZ as a default because presumably it is good Xfor the system. X*/ X#define BT_DFLTPSIZ BUFSIZ X X/* Xdefault magic number to use, unless a user supplies us one. Xthis can come in handy if you add it to your file(1) types Xdatabase. X*/ X#define BT_DFLTMAGIC 72251L X X/* Xdefault number of cache pages to ADD to the minimum page cache Xdo NOT simply edit this value here, since it can be set in Xcalls to bt_optopen() using BT_CACHE on a case-by-case basis. Xremember also that there are (about 4) cache buffers that will Xbe allocated no matter what, so this value is in addition to Xthe minimum cache. the minimum cache buffers are used for Xsplitting and promotion as well as page buffers, depending Xon what is being done. cache size can be overruled upwards Xby the user, so a sensible value is good here. X*/ X#define BT_DFLTCACHE 1 X X/* Xdefault type of caching: read only - IE pages will always write to Xdisk when modified, but may be read out of cache directly. using Xread-only caching is the safe bet. whatever default is selected Xhere can be overruled by the user, so a safe value is OK here. X*/ X#define BT_DFLTCFLAG BT_ROCACHE X X/* Xdefault data type to store: strings are a pretty good bet. this can Xbe reset anyhow in bt_optopen(), so leaving it alone is recommended. XWARNING - do not set this to be BT_USRDEF! bt_open() does not have Xany way of setting the function pointer for the comparison function. Xusing the BT_STRING data type should be encouraged anyhow, since Xstring keys can be prefixed for greater efficiency. X*/ X#define BT_DFLTDTYPE BT_STRING X X/* Xthat is all. this file does not need to be installed where a user Xcan include it. X*/ X X#define _DEF_BT_CONFIG_H X#endif END_OF_FILE if test 4357 -ne `wc -c <'b+tree/btlib/btconf.h'`; then echo shar: \"'b+tree/btlib/btconf.h'\" unpacked with wrong size! fi # end of 'b+tree/btlib/btconf.h' fi if test -f 'b+tree/btlib/btdebug.c' -a "${1}" != "-c" ; then echo shar: Will not clobber existing file \"'b+tree/btlib/btdebug.c'\" else echo shar: Extracting \"'b+tree/btlib/btdebug.c'\" $1897 characters$ sed "s/^X//" >'b+tree/btlib/btdebug.c' <<'END_OF_FILE' X#include <stdio.h> X#include <sys/types.h> X#include "btconf.h" X#include "btree.h" X#include "btintern.h" X X/* X (C) Copyright, 1988, 1989 Marcus J. Ranum X All rights reserved X X X This software, its documentation, and supporting X files are copyrighted material and may only be X distributed in accordance with the terms listed in X the COPYRIGHT document. X*/ X X X#ifdef YES_BT_DEBUG X#ifndef lint Xstatic char *rcsid = "$Header: /atreus/mjr/hacks/btree/btlib/RCS/btdebug.c,v 1.1 89/10/24 10:08:55 mjr Rel $"; X#endif X Xvoid Xbt_dump(b,p) XBT_INDEX *b; Xstruct bt_cache *p; X{ X int x; X int rl; X off_t rv; X char buf[BT_DFLTPSIZ]; X X if(KEYUSE(p->p) > bt_pagesiz(b)) X (void)printf("WARNING overfull page!!!\n"); X X X (void)printf("Dump:page=%ld, cnt=%d, len=%d, ", X p->num,KEYCNT(p->p),KEYLEN(p->p)); X X (void)printf("lsib=%ld, rsib=%ld, high=%ld, used=%d\n", X LSIB(p->p),RSIB(p->p),HIPT(p->p),KEYUSE(p->p)); X X if(BT_MAXK(b) > sizeof(buf)) { X (void)printf("page size too big to dump keys (sorry)\n"); X return; X } X X /* print keys/len/chld index */ X for(x = 0; x < KEYCNT(p->p); x++) { X if(bt_keyof(x,p->p,(bt_chrp)buf,&rl,&rv,(int)sizeof(buf)) == BT_ERR) { X (void)printf("cannot access key #%d\n",x); X return; X } X X switch(bt_dtype(b)) { X case BT_STRING: X buf[rl] = '\0'; X (void)printf("key=\"%s\",len=%d,rrv=%ld",buf,rl,rv); X break; X X case BT_INT: X (void)printf("key=%d,len=%d,rrv=%ld",*(int *)buf,rl,rv); X break; X X case BT_LONG: X (void)printf("key=%ld,len=%d,rrv=%ld",*(long *)buf,rl,rv); X break; X X case BT_FLOAT: X (void)printf("key=%f,len=%d,rrv=%ld",*(float *)buf,rl,rv); X break; X X case BT_USRDEF: X (void)printf("key=<usrdef>,len=%d,rrv=%ld",rl,rv); X break; X } X X if(x % 4 == 3) X (void)printf("\n"); X else X if(x != KEYCNT(p->p) - 1) X (void)printf(", "); X } X (void)printf("\n"); X} X#endif END_OF_FILE if test 1897 -ne `wc -c <'b+tree/btlib/btdebug.c'`; then echo shar: \"'b+tree/btlib/btdebug.c'\" unpacked with wrong size! fi # end of 'b+tree/btlib/btdebug.c' fi if test -f 'b+tree/btlib/btdelete.c' -a "${1}" != "-c" ; then echo shar: Will not clobber existing file \"'b+tree/btlib/btdelete.c'\" else echo shar: Extracting \"'b+tree/btlib/btdelete.c'\" $4335 characters$ sed "s/^X//" >'b+tree/btlib/btdelete.c' <<'END_OF_FILE' X#include <sys/types.h> X#include <stdio.h> X#include "btconf.h" X#include "btree.h" X#include "btintern.h" X X/* X (C) Copyright, 1988, 1989 Marcus J. Ranum X All rights reserved X X X This software, its documentation, and supporting X files are copyrighted material and may only be X distributed in accordance with the terms listed in X the COPYRIGHT document. X*/ X X#ifndef lint Xstatic char *rcsid = "$Header: /atreus/mjr/hacks/btree/btlib/RCS/btdelete.c,v 1.1 89/10/24 10:08:56 mjr Rel $"; X#endif X X Xbt_delete(b,key,len) XBT_INDEX *b; Xbt_chrp key; Xint len; X{ X struct bt_cache *op; X int staklev; X off_t dpag; /* page to delete from */ X int keyat; /* key # to delete */ X off_t ptj; /* junk */ X int sr; X X /* 90% of this code is straight from bt_insert(). the only */ X /* difference is that we need to ensure an exact match at */ X /* leaf level only, otherwise we just track our way up the */ X /* tree, deleting keys. page concatenation and redistribution */ X /* are not implemented, though if they are to be, they should */ X /* fit fairly easily in this framework. good luck, deletes suck */ X X /* the usual consistency checks */ X if(len > BT_MAXK(b)) { X bt_errno(b) = BT_KTOOBIG; X return(BT_ERR); X } X X if(len <= 0) { X bt_errno(b) = BT_ZEROKEY; X return(BT_ERR); X } X X if(bt_seekdown(b,key,len) == BT_ERR) X return(BT_ERR); X X /* set current stack level */ X staklev = b->sblk.levs - 1; X dpag = b->stack[staklev].pg; X X if((op = bt_rpage(b,dpag)) == NULL) X return(BT_ERR); X X /* locate first del point, check if not there */ X /* there must not be anything to delete. error. */ X sr = bt_srchpg(key,len,bt_dtype(b),b->cmpfn,&ptj,&keyat,op->p); X if(sr == BT_NF) X return(BT_NF); X if(sr == BT_ERR) { X bt_errno(b) = BT_PAGESRCH; X return(BT_ERR); X } X X /* invalidate current notion of where we are in the tree */ X b->cpag = BT_NULL; X X /* this loop should be comfortably repeated until we perform a */ X /* simple delete without emptying a page. if a page concatentation */ X /* function is added, we would look until we no longer concatenate */ X while(1) { X X /* oddball special case. if the page is root and */ X /* there is no key left to delete, the tree is */ X /* (by definition) empty, having only a high pointer */ X /* left. so, the high pointer is dropped, and */ X /* turned to BT_NULL, instantly converting root */ X /* back to a leaf page. we then return. done */ X if(dpag == b->sblk.root && KEYCNT(op->p) == 0) { X HIPT(op->p) = BT_NULL; X KEYLEN(op->p) = 0; X op->flags = BT_CHE_DIRTY; X if(bt_wpage(b,op) == BT_ERR) X return(BT_ERR); X b->sblk.levs = 1; X if(bt_wsuper(b) == BT_ERR) X return(BT_ERR); X return(BT_OK); X } X X /* if the page has more than one key OR is an index with */ X /* one key, just drop one key from the page, do not free it */ X /* also, if the page is the root page, do not do free it */ X if(KEYCNT(op->p) > 1 || dpag == b->sblk.root || X (KEYCNT(op->p) == 1 && HIPT(op->p) != BT_NULL)) { X struct bt_cache *tp; /* temp copy page */ X X if((tp = bt_rpage(b,BT_NULL)) == NULL) X return(BT_ERR); X bt_delpg(keyat,op->p,tp->p); X X /* swap the page numbers, invalidate the old, */ X /* mark the new as dirty to force a write */ X tp->num = op->num; X tp->flags = BT_CHE_DIRTY; X op->num = BT_NULL; X X if(bt_wpage(b,op) == BT_ERR || bt_wpage(b,tp) == BT_ERR) X return(BT_ERR); X X /* mark all as well with tree */ X bt_clearerr(b); X return(BT_OK); X } else { X off_t savlft; X off_t savrt; X X savlft = LSIB(op->p); X savrt = RSIB(op->p); X X if(savlft != BT_NULL) { X if((op = bt_rpage(b,savlft)) == NULL) X return(BT_ERR); X RSIB(op->p) = savrt; X op->flags = BT_CHE_DIRTY; X if(bt_wpage(b,op) == BT_ERR) X return(BT_ERR); X } X X if(savrt != BT_NULL) { X if((op = bt_rpage(b,savrt)) == NULL) X return(BT_ERR); X LSIB(op->p) = savlft; X op->flags = BT_CHE_DIRTY; X if(bt_wpage(b,op) == BT_ERR) X return(BT_ERR); X } X X /* sibs are fixed, now free the page */ X if(bt_freepage(b,dpag) == BT_ERR) X return(BT_ERR); X } X X /* still going, pop stack level */ X staklev--; X X /* set key location for next delete */ X keyat = b->stack[staklev].ky; X dpag = b->stack[staklev].pg; X X /* allocate a scratch page and read the old */ X if((op = bt_rpage(b,dpag)) == NULL) X return(BT_ERR); X X } X} END_OF_FILE if test 4335 -ne `wc -c <'b+tree/btlib/btdelete.c'`; then echo shar: \"'b+tree/btlib/btdelete.c'\" unpacked with wrong size! fi # end of 'b+tree/btlib/btdelete.c' fi if test -f 'b+tree/btlib/btload.c' -a "${1}" != "-c" ; then echo shar: Will not clobber existing file \"'b+tree/btlib/btload.c'\" else echo shar: Extracting \"'b+tree/btlib/btload.c'\" $4231 characters$ sed "s/^X//" >'b+tree/btlib/btload.c' <<'END_OF_FILE' X#include <sys/types.h> X#include <stdio.h> X#include "btconf.h" X#include "btree.h" X#include "btintern.h" X X/* X (C) Copyright, 1988, 1989 Marcus J. Ranum X All rights reserved X X X This software, its documentation, and supporting X files are copyrighted material and may only be X distributed in accordance with the terms listed in X the COPYRIGHT document. X*/ X X X#ifndef lint Xstatic char *rcsid = "$Header: /atreus/mjr/hacks/btree/btlib/RCS/btload.c,v 1.1 89/10/24 10:08:59 mjr Rel $"; X#endif X Xextern char *realloc(); X Xbt_load(b,key,len,rrn,flag) XBT_INDEX *b; Xbt_chrp key; Xint len; Xoff_t rrn; Xint flag; X{ X struct bt_cache *op = NULL; X struct bt_cache *np = NULL; X off_t irrn; X off_t savold = BT_NULL; X int slev; X X /* first insert is always at leaf lev. */ X /* note that we use the stack backwards here */ X slev = 0; X X irrn = rrn; X X /* if flag is BOF, zap the tree and ready for load */ X if(flag == BT_BOF) { X return(bt_zap(b)); X } X X /* if flag is BT_EOF close up and finish the tree */ X if(flag == BT_EOF) { X return(BT_OK); X } X X /* if the flag is wrong, die. */ X if(flag != BT_OK) { X bt_errno(b) = BT_BADUSERARG; X return(BT_ERR); X } X X /* safety valves */ X if(len > BT_MAXK(b)) { X bt_errno(b) = BT_KTOOBIG; X return(BT_ERR); X } X X if(len <= 0) { X bt_errno(b) = BT_ZEROKEY; X return(BT_ERR); X } X X /* set the bottom of the stack */ X b->stack[b->sblk.levs - 1].pg = b->sblk.root; X X X /* this is similar to insert, but simpler */ X while(1) { X X if((op = bt_rpage(b,b->stack[slev].pg)) == NULL) X goto bombout; X X /* if key will fit in page, perform simple insert */ X if((int)KEYUSE(op->p) + len + sizeof(int) + sizeof(off_t) < bt_pagesiz(b)) { X if((np = bt_rpage(b,BT_NULL)) == NULL) X goto bombout; X X bt_inspg(key,len,&irrn,0,op->p,np->p); X X /* adjust caching and write */ X np->num = op->num; X np->flags = BT_CHE_DIRTY; X op->num = BT_NULL; X X if(bt_wpage(b,op) == BT_ERR || bt_wpage(b,np) == BT_ERR) X return(BT_ERR); X X /* e finito */ X bt_clearerr(b); X return(BT_OK); X } else { X off_t npag; X int indexsplit = 0; X X if((npag = bt_newpage(b)) == BT_NULL) X goto bombout; X X if(HIPT(op->p) != BT_NULL) X indexsplit++; X X /* fix up left sib in old page and start new */ X LSIB(op->p) = npag; X op->flags = BT_CHE_DIRTY; X X if(bt_wpage(b,op) == BT_ERR) X goto bombout; X X if((np = bt_rpage(b,BT_NULL)) == NULL) X goto bombout; X X KEYCNT(np->p) = KEYLEN(np->p) = 0; X RSIB(np->p) = b->stack[slev].pg; X LSIB(np->p) = HIPT(np->p) = BT_NULL; X X if(!indexsplit) { X if((op = bt_rpage(b,BT_NULL)) == NULL) X goto bombout; X X bt_inspg(key,len,&irrn,0,np->p,op->p); X np->num = BT_NULL; X op->num = npag; X op->flags = BT_CHE_DIRTY; X if(bt_wpage(b,np) == BT_ERR || X bt_wpage(b,op) == BT_ERR) X goto bombout; X } else { X HIPT(np->p) = irrn; X np->num = npag; X np->flags = BT_CHE_DIRTY; X if(bt_wpage(b,np) == BT_ERR) X goto bombout; X } X X /* new rrn is new page */ X irrn = npag; X X /* new current page is the new page */ X /* at this point the old one is history */ X savold = b->stack[slev].pg; X b->stack[slev].pg = npag; X } X X /* pop down a level (really up) */ X slev++; X /* dynamically deal w/ stack overruns */ X if(b->sblk.levs == b->shih - 2) { X b->shih += 3; X b->stack = (struct bt_stack *)realloc((char *)b->stack,(unsigned)(b->shih * sizeof(struct bt_stack))); X if(b->stack == NULL) X return(BT_ERR); X } X X /* do we need a new root page ? */ X if(slev == b->sblk.levs) { X if((b->sblk.root = bt_newpage(b)) == BT_NULL) X goto bombout; X X if((op = bt_rpage(b,BT_NULL)) == NULL) X goto bombout; X X /* set it up as blank except the high pointer */ X /* on the next iteration, the key will be inserted */ X LSIB(op->p) = RSIB(op->p) = BT_NULL; X KEYLEN(op->p) = KEYCNT(op->p) = 0; X HIPT(op->p) = savold; X X op->num = b->sblk.root; X op->flags = BT_CHE_DIRTY; X X b->dirt++; X b->sblk.levs++; X X b->stack[b->sblk.levs - 1].pg = b->sblk.root; X if(bt_wpage(b,op) == BT_ERR || bt_wsuper(b) == BT_ERR) X goto bombout; X } X } X X /* argh ! */ Xbombout: X if(op != NULL) X (void)bt_wpage(b,op); X if(np != NULL) X (void)bt_wpage(b,np); X return(BT_ERR); X} END_OF_FILE if test 4231 -ne `wc -c <'b+tree/btlib/btload.c'`; then echo shar: \"'b+tree/btlib/btload.c'\" unpacked with wrong size! fi # end of 'b+tree/btlib/btload.c' fi if test -f 'b+tree/btlib/btopen.c' -a "${1}" != "-c" ; then echo shar: Will not clobber existing file \"'b+tree/btlib/btopen.c'\" else echo shar: Extracting \"'b+tree/btlib/btopen.c'\" $3058 characters$ sed "s/^X//" >'b+tree/btlib/btopen.c' <<'END_OF_FILE' X#include <sys/types.h> X#include <sys/file.h> X#include <stdio.h> X#include "btconf.h" X#include "btree.h" X#include "btintern.h" X X/* X (C) Copyright, 1988, 1989 Marcus J. Ranum X All rights reserved X X X This software, its documentation, and supporting X files are copyrighted material and may only be X distributed in accordance with the terms listed in X the COPYRIGHT document. X*/ X X X#ifndef lint Xstatic char *rcsid = "$Header: /atreus/mjr/hacks/btree/btlib/RCS/btopen.c,v 1.1 89/10/24 10:09:00 mjr Rel $"; X#endif X Xextern char *malloc(); Xextern off_t lseek(); X X XBT_INDEX * Xbt_open(path,flags,mode) Xchar *path; Xint flags; Xint mode; X{ X BT_INDEX *ret; X struct bt_cache *cp1; X struct bt_cache *cp2; X int r; X X if((ret = (BT_INDEX *)malloc(sizeof(BT_INDEX))) == NULL) X return(NULL); X X /* clear error */ X bt_errno(ret) = BT_NOERROR; X X /* set funcp to something inoffensive */ X bt_cmpfn(ret) = 0; X X if((bt_fileno(ret) = open(path,(flags|O_RDWR),mode)) < 0) X goto bombout; X X r = read(bt_fileno(ret),(char *)&ret->sblk,sizeof(struct bt_super)); X X /* failure to read anything - initialize tree */ X if(r == 0) { X char *jnk; X if((jnk = malloc((unsigned)BT_DFLTPSIZ)) != NULL) { X ret->sblk.magic = BT_DFLTMAGIC; X bt_pagesiz(ret) = BT_DFLTPSIZ; X bt_dtype(ret) = BT_DFLTDTYPE; X ret->sblk.levs = 1; X ret->sblk.root = (off_t)BT_DFLTPSIZ; X ret->sblk.free = BT_NULL; X ret->sblk.high = (off_t)(2 * BT_DFLTPSIZ); X X /* mark super block as dirty and sync */ X ret->dirt = 1; X X /* write and pretend we read a legit superblock */ X if(bt_wsuper(ret) == BT_OK) X r = sizeof(struct bt_super); X X /* now make jnk into an empty first page */ X KEYCNT(jnk) = 0; X KEYLEN(jnk) = 0; X LSIB(jnk) = RSIB(jnk) = BT_NULL; X HIPT(jnk) = BT_NULL; X X /* now, since the cache is not set up yet, we */ X /* must directly write the page. */ X if(lseek(bt_fileno(ret),(off_t)BT_DFLTPSIZ,SEEK_SET) != (off_t)BT_DFLTPSIZ || X write(bt_fileno(ret),jnk,BT_DFLTPSIZ) != BT_DFLTPSIZ) X r = 0; X (void)free(jnk); X } X } X X /* yet another sanity check */ X if(r != sizeof(struct bt_super) || ret->sblk.magic != BT_DFLTMAGIC) X goto bombout; X X /* initialize locator stack */ X ret->shih = ret->sblk.levs + 2; X ret->stack = (struct bt_stack *)malloc((unsigned)(ret->shih * sizeof(struct bt_stack))); X if(ret->stack == NULL) X goto bombout; X X /* initialize cache */ X cp2 = ret->lru = NULL; X for(r = 0; r < BT_MINCACHE + BT_DFLTCACHE; r++) { X cp1 = (struct bt_cache *)malloc(sizeof(struct bt_cache)); X if(cp1 == NULL) X goto bombout; X X if(ret->lru == NULL) X ret->lru = cp1; X cp1->prev = cp2; X cp1->num = BT_NULL; X cp1->next = NULL; X cp1->flags = BT_CHE_CLEAN; X if((cp1->p = (bt_chrp)malloc((unsigned)bt_pagesiz(ret))) == NULL) X goto bombout; X if(cp2 != NULL) X cp2->next = cp1; X X cp2 = cp1; X } X ret->mru = cp1; X X /* set cache type flag */ X ret->cflg = BT_DFLTCFLAG; X X /* no valid current key */ X ret->cpag = BT_NULL; X X /* all is well */ X return(ret); X Xbombout: X (void)bt_close(ret); X return(NULL); X} END_OF_FILE if test 3058 -ne `wc -c <'b+tree/btlib/btopen.c'`; then echo shar: \"'b+tree/btlib/btopen.c'\" unpacked with wrong size! fi # end of 'b+tree/btlib/btopen.c' fi if test -f 'b+tree/btlib/btravrs.c' -a "${1}" != "-c" ; then echo shar: Will not clobber existing file \"'b+tree/btlib/btravrs.c'\" else echo shar: Extracting \"'b+tree/btlib/btravrs.c'\" $1977 characters$ sed "s/^X//" >'b+tree/btlib/btravrs.c' <<'END_OF_FILE' X#include <sys/types.h> X#include <stdio.h> X#include "btconf.h" X#include "btree.h" X#include "btintern.h" X X/* X (C) Copyright, 1988, 1989 Marcus J. Ranum X All rights reserved X X X This software, its documentation, and supporting X files are copyrighted material and may only be X distributed in accordance with the terms listed in X the COPYRIGHT document. X*/ X X X#ifndef lint Xstatic char *rcsid = "$Header: /atreus/mjr/hacks/btree/btlib/RCS/btravrs.c,v 1.1 89/10/24 10:09:06 mjr Rel $"; X#endif X Xbt_traverse(b,d,kbuf,maxlen,retlen,retrrv) XBT_INDEX *b; Xint d; Xbt_chrp kbuf; Xint maxlen; Xint *retlen; Xoff_t *retrrv; X{ X struct bt_cache *p; X off_t savp; X X /* if the current page is not set, just zing up to the head */ X /* or the tail - the opposite side of the tree, whatever it is */ X if(b->cpag == BT_NULL) X if(bt_goto(b,d == BT_EOF ? BT_BOF:BT_EOF) == BT_ERR) X return(BT_ERR); X X /* save */ X savp = b->cpag; X X if((p = bt_rpage(b,b->cpag)) == NULL) X return(BT_ERR); X X /* adjust current key # */ X if(d == BT_EOF) X b->cky++; X else X b->cky--; X X /* have we run out of keys in the page ? */ X while((d == BT_EOF && b->cky >= KEYCNT(p->p)) || X (d == BT_BOF && b->cky < 0)) { X X if(d == BT_EOF) X b->cpag = RSIB(p->p); X else X b->cpag = LSIB(p->p); X X /* we are there - wherever there is */ X if(b->cpag != BT_NULL) { X if((p = bt_rpage(b,b->cpag)) == NULL) X return(BT_ERR); X X /* reset current key */ X if(d == BT_EOF) X b->cky = 0; X else X b->cky = KEYCNT(p->p) - 1; X } else { X /* we have actually HIT the end */ X /* restore current page */ X b->cpag = savp; X /* and point the key just past the end of the page */ X if(d == BT_EOF) X b->cky = KEYCNT(p->p); X else X b->cky = -1; X *retlen = 0; X *retrrv = 0; X return(d); X } X } X X if(bt_keyof(b->cky,p->p,kbuf,retlen,retrrv,maxlen) == BT_ERR) X return(BT_ERR); X X /* mark all as well with tree */ X bt_clearerr(b); X return(BT_OK); X} END_OF_FILE if test 1977 -ne `wc -c <'b+tree/btlib/btravrs.c'`; then echo shar: \"'b+tree/btlib/btravrs.c'\" unpacked with wrong size! fi # end of 'b+tree/btlib/btravrs.c' fi if test -f 'b+tree/btlib/btree.h' -a "${1}" != "-c" ; then echo shar: Will not clobber existing file \"'b+tree/btlib/btree.h'\" else echo shar: Extracting \"'b+tree/btlib/btree.h'\" $2984 characters$ sed "s/^X//" >'b+tree/btlib/btree.h' <<'END_OF_FILE' X#ifndef _DEF_BTREE_H X X/* X (C) Copyright, 1988, 1989 Marcus J. Ranum X All rights reserved X X X This software, its documentation, and supporting X files are copyrighted material and may only be X distributed in accordance with the terms listed in X the COPYRIGHT document. X*/ X X X/* X $Header: /atreus/mjr/hacks/btree/btlib/RCS/btree.h,v 1.1 89/10/24 10:09:07 mjr Rel $ X*/ X X X/* Xthere are some potential problems with just using char * instead of Xunsigned char *, because of sign extension and so on. the following Xtypedef indicates the best type to use as a pointer to an arbitrary Xchunk of data for the system. since a lot of pointer math is done on Xthese, it should be either a signed or unsigned char, or odd results Xmay occur. Xtypedef char * bt_chrp; X*/ Xtypedef unsigned char * bt_chrp; X X X/* return codes */ X#define BT_OK 0 X#define BT_ERR -1 X#define BT_NF 1 X#define BT_EOF 2 X#define BT_BOF 3 X X/* arguments to bt_optopen */ X#define BT_PATH 1 X#define BT_PSIZE 2 X#define BT_CACHE 3 X#define BT_CFLAG 4 X#define BT_OMODE 5 X#define BT_OPERM 6 X#define BT_MAGIC 7 X#define BT_DTYPE 8 X#define BT_LABEL 9 X X/* cache modes, acceptable argument to BT_CFLAG */ X#define BT_NOCACHE 0 X#define BT_ROCACHE 1 X#define BT_RWCACHE 2 X X/* recognized data types, acceptable argument to BT_DTYPE */ X#define BT_STRING 0 X#define BT_INT 1 X#define BT_LONG 2 X#define BT_FLOAT 3 X#define BT_USRDEF 4 X X/* cache handle */ Xstruct bt_cache { X char flags; X bt_chrp p; X off_t num; X struct bt_cache *next; X struct bt_cache *prev; X}; X X/* super block */ Xstruct bt_super { X long magic; X int psiz; X int levs; X int dtyp; X off_t root; X off_t free; X off_t high; X}; X Xstruct bt_stack { X off_t pg; X int ky; X}; X X/* b+tree index handle */ Xstruct bt_index { X int fd; X int errno; X char dirt; X int cflg; X int cky; X off_t cpag; X int (*cmpfn)(); X struct bt_super sblk; X struct bt_cache *lru; X struct bt_cache *mru; X struct bt_stack *stack; X int shih; X}; X#define BT_INDEX struct bt_index X X/* pseudo functions */ X#define bt_fileno(b) (b->fd) X#define bt_pagesiz(b) (b->sblk.psiz) X#define bt_dtype(b) (b->sblk.dtyp) X#define bt_cmpfn(b) (b->cmpfn) X#define bt_errno(b) (b->errno) X#define bt_clearerr(b) (b->errno = BT_NOERROR) X X/* biggest size of a key - depends on the page size of the tree */ X#define BT_MAXK(b) (((b->sblk.psiz-(4*sizeof(int))-(5*sizeof(off_t)))/2) - sizeof(off_t)) X X/* size of page 0 label - depends on the page size and sblk size */ X#define BT_LABSIZ(b) (b->sblk.psiz - (sizeof(struct bt_super) + 1)) X X/* forward decls. */ Xextern BT_INDEX *bt_open(); Xextern BT_INDEX *bt_optopen(); Xextern void bt_perror(); X X/* btree error codes and messages */ Xextern char *bt_errs[]; X X/* error constants */ X#define BT_NOERROR 0 X#define BT_KTOOBIG 1 X#define BT_ZEROKEY 2 X#define BT_DUPKEY 3 X#define BT_PTRINVAL 4 X#define BT_NOBUFFERS 5 X#define BT_LTOOBIG 6 X#define BT_BTOOSMALL 7 X#define BT_BADPAGE 8 X#define BT_PAGESRCH 9 X#define BT_BADUSERARG 10 X X#define _DEF_BTREE_H X#endif END_OF_FILE if test 2984 -ne `wc -c <'b+tree/btlib/btree.h'`; then echo shar: \"'b+tree/btlib/btree.h'\" unpacked with wrong size! fi # end of 'b+tree/btlib/btree.h' fi if test -f 'b+tree/utils/Makefile' -a "${1}" != "-c" ; then echo shar: Will not clobber existing file \"'b+tree/utils/Makefile'\" else echo shar: Extracting \"'b+tree/utils/Makefile'\" $1773 characters$ sed "s/^X//" >'b+tree/utils/Makefile' <<'END_OF_FILE' X# X# X#/* X# (C) Copyright, 1988, 1989 Marcus J. Ranum X# All rights reserved X# X# X# This software, its documentation, and supporting X# files are copyrighted material and may only be X# distributed in accordance with the terms listed in X# the COPYRIGHT document. X#*/ X# X# $Header: /atreus/mjr/hacks/btree/utils/RCS/Makefile,v 1.1 89/10/24 10:09:30 mjr Rel $ X# X XBTHDRDIR=../btlib XDBHDRDIR=../btdbmlib X XLIBDIR=.. XBTLIB= $(LIBDIR)/libbtree.a XDBLIB= $(LIBDIR)/libbtdbm.a X X# if compiled with -DBTOPEN test programs will use simpler version X# of open that is smaller and has less frills X# if compiled with -DDEBUG, testrack will give an idea of what is X# going on inside X XCC= cc X X#CFLAGS = -I$(BTHDRDIR) -I$(DBHDRDIR) -g X#CFLAGS = -I$(BTHDRDIR) -I$(DBHDRDIR) -p -DDEBUG XCFLAGS = -I$(BTHDRDIR) -I$(DBHDRDIR) -O X XLDFLAGS = -p X#LDFLAGS = -s X X XCFILES= testrack.c \ X words.c \ X btoptim.c \ X rectest.c \ X dbtest.c \ X btest.c X Xall: testrack btest rectest dbtest words btoptim X Xtestrack: testrack.o $(BTLIB) X $(CC) $(LDFLAGS) -o testrack testrack.o $(BTLIB) X Xbtest: btest.o $(BTLIB) X $(CC) $(LDFLAGS) -o btest btest.o $(BTLIB) X Xrectest: rectest.o $(DBLIB) X $(CC) $(LDFLAGS) -o rectest rectest.o $(DBLIB) X Xdbtest: dbtest.o $(DBLIB) $(BTLIB) X $(CC) $(LDFLAGS) -o dbtest dbtest.o $(DBLIB) $(BTLIB) X Xwords: words.o X $(CC) $(LDFLAGS) -o words words.o X Xbtoptim: btoptim.o $(BTLIB) X $(CC) $(LDFLAGS) -o btoptim btoptim.o $(BTLIB) X Xflog: testrack words flog.sh X sh flog.sh X Xclean: X rm -f testrack words btest *.o core input input.srt test.dat \ X test2.dat btoptim rectest dbtest X Xlint: X lint -I$(BTHDRDIR) -I$(DBHDRDIR) -u $(CFILES) | sed '/pointer alignment/d' X Xci: clean X ci -u $(CFILES) flog.sh Makefile README < /dev/null END_OF_FILE if test 1773 -ne `wc -c <'b+tree/utils/Makefile'`; then echo shar: \"'b+tree/utils/Makefile'\" unpacked with wrong size! fi # end of 'b+tree/utils/Makefile' fi if test -f 'b+tree/utils/README' -a "${1}" != "-c" ; then echo shar: Will not clobber existing file \"'b+tree/utils/README'\" else echo shar: Extracting \"'b+tree/utils/README'\" $1953 characters$ sed "s/^X//" >'b+tree/utils/README' <<'END_OF_FILE' X X X/* X (C) Copyright, 1988, 1989 Marcus J. Ranum X All rights reserved X X X This software, its documentation, and supporting X files are copyrighted material and may only be X distributed in accordance with the terms listed in X the COPYRIGHT document. X*/ X X The test program "btflog.sh" is a good way of seeing if Xthe btree routines work on your system. for the first test runs Xyou may wish to edit some of the parameters at the top of btflog.sh X- or just type "make flog" and watch. X X X XContents:: XMakefile - self explanatory. X XREADME - this. X Xbtest.c - test harness and btree debugger (of sorts). this X program breaks a lot of rules, by making use of X some of the internal b+tree functions. at least X if you're going to do it, you'll have some examples. X Do NOT use btest as a means of judging the speed X of the library, since the input-interpreting X routines in it are pretty slow. X Xdbtest.c - test harness for the dbm-clone library built on X the store library. X Xrectest.c - test harness for the store library. X Xflog.sh - a bourne shell script that pounds an index or two on X its head by having randwords make a list of garbage, and X then inserting it, deleting it, and so on. X Xwords.c - junk word maker for btree test rack. X Xbtoptim.c - a simple program that copies one index out, in X reverse sort order, and does an optimal load X of the index into a new one. X Xtestrack.c - test driver containing several different tests, X each of which tries to match the expected state of X the tree against the real state, and so on. the X key values to change when flogging the code are the X number and length of random words to insert, and X the page size of the test trees. X XNotes: X the code in btest.c uses a few icky hackerish tricks, X but is intended to be simple to use and follow. I X tried to pretty well do one of everything, to provide X examples. X XTo Do: X ?? X X--mjr(); END_OF_FILE if test 1953 -ne `wc -c <'b+tree/utils/README'`; then echo shar: \"'b+tree/utils/README'\" unpacked with wrong size! fi # end of 'b+tree/utils/README' fi if test -f 'b+tree/utils/btoptim.c' -a "${1}" != "-c" ; then echo shar: Will not clobber existing file \"'b+tree/utils/btoptim.c'\" else echo shar: Extracting \"'b+tree/utils/btoptim.c'\" $3186 characters$ sed "s/^X//" >'b+tree/utils/btoptim.c' <<'END_OF_FILE' X#include <stdio.h> X#include <ctype.h> X#include <sys/types.h> X#include <sys/file.h> X#include "btree.h" X X/* X (C) Copyright, 1988, 1989 Marcus J. Ranum X All rights reserved X X X This software, its documentation, and supporting X files are copyrighted material and may only be X distributed in accordance with the terms listed in X the COPYRIGHT document. X*/ X X/* X This program optimizes an index by recopying it into a X new one using a reverse load X*/ X Xextern char *malloc(); X Xmain(ac,av) Xint ac; Xchar *av[]; X{ X BT_INDEX *old; X BT_INDEX *new; X char *infile; X char *outfile; X int outpsiz = -1; /* output page size */ X off_t rrnstore; X int lenstore; X bt_chrp bufptr; /* have to allocate this dynamically */ X /* in case the tree has BIG pages */ X int ret; X X for(ret = 1; ret < ac; ret++) { X if(av[ret][0] == '-') X switch(av[ret][1]) { X case 'p': X outpsiz = atoi(av[ret + 1]); X if(outpsiz == 0) { X (void)fprintf(stderr,"%s: page size must be an integer > 0\n",av[0]); X outpsiz = -1; X } X break; X X case 'o': X outfile = av[ret + 1]; X break; X X case 'i': X infile = av[ret + 1]; X break; X X default: X exit(usage()); X } X } X X if(outfile == NULL || infile == NULL) X exit(usage()); X X#ifdef BTOPEN X old = bt_open(infile,O_RDONLY,0600); X#else X old = bt_optopen(BT_PATH, infile, X BT_OMODE, O_RDONLY, X 0); X#endif X X if(old == NULL) { X perror(infile); X exit(1); X } X X /* if output page size was not set on the command line, adopt old */ X if(outpsiz == -1) X outpsiz = bt_pagesiz(old); X X if((bufptr = (bt_chrp)malloc((unsigned)bt_pagesiz(old))) == NULL) { X perror("cannot allocate buffer memory"); X (void)bt_close(old); X exit(1); X } X X#ifdef BTOPEN X new = bt_open(av[2],O_CREAT|O_TRUNC,0600); X#else X new = bt_optopen(BT_PATH, outfile, X BT_OMODE, O_CREAT|O_TRUNC, X BT_OPERM, 0600, X BT_CACHE, 3, X BT_PSIZE, outpsiz, X BT_CFLAG, BT_RWCACHE, X 0); X#endif X X if(new == NULL) { X perror(outfile); X exit(1); X } X X /* inform the new file we are going to bt_load it */ X if(bt_load(new,0,0,0L,BT_BOF)== BT_ERR) { X bt_perror(new,"initialize load"); X exit(1); X } X X /* since we have not performed any traverses yet, it will start */ X /* at the END of the index, automatically - nifty that, ey? */ X /* REMEMBER, this HAS to be REVERSE order !!! */ X while((ret = bt_traverse(old,BT_BOF,bufptr,bt_pagesiz(old),&lenstore,&rrnstore)) == BT_OK) { X if(bt_load(new,bufptr,lenstore,rrnstore,BT_OK)== BT_ERR) { X bt_perror(new,"bt_load"); X exit(1); X } X } X if(ret != BT_BOF) { X (void)fprintf(stderr,"warning: traverse did not complete at BOF!\n"); X } X X /* a final call to bt_load with BT_EOF tells it to stop */ X if(bt_load(new,0,0,0L,BT_EOF) == BT_ERR) { X bt_perror(new,"shut down load"); X exit(1); X } X X if(bt_close(old) != BT_OK || bt_close(new) != BT_OK) { X (void)fprintf(stderr,"error closing indices\n"); X exit(1); X } X X (void)free((char *)bufptr); X exit(0); X} X Xusage() X{ X (void)fprintf(stderr,"usage: btoptim -i input -o output [-p page size]\n"); X (void)fprintf(stderr,"where input and output are b+tree indices, and page size a positive integer\n"); X return(1); X} END_OF_FILE if test 3186 -ne `wc -c <'b+tree/utils/btoptim.c'`; then echo shar: \"'b+tree/utils/btoptim.c'\" unpacked with wrong size! fi # end of 'b+tree/utils/btoptim.c' fi echo shar: End of archive 2 $of 5$. cp /dev/null ark2isdone MISSING="" for I in 1 2 3 4 5 ; do if test ! -f ark${I}isdone ; then MISSING="${MISSING} ${I}" fi done if test "${MISSING}" = "" ; then echo You have unpacked all 5 archives. rm -f ark[1-9]isdone else echo You still need to unpack the following archives: echo " " ${MISSING} fi ## End of shell archive. exit 0